package Solution101_200.problem114.FlattenBinaryTreetoLinkedList;

import common.TreeNode;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/07/15 15:12
 */
public class Solution {
    private TreeNode prev = null;
    public void flatten(TreeNode root) {
        if(root == null) return;
        TreeNode right = root.right;
        //必需保存起来，要不然就在flatten左子节点时被更新了
        if(prev != null) {
            prev.left = null;
            //因为更新左子节点的时候，左子节点已经拿到，故不用特殊保存
            prev.right = root;
            //因为前序遍历，右子节点最后访问，此时右子节点已保存，可更新
        }
        prev = root;
        flatten(root.left);
        flatten(right);
        //注意，这个地方不能是root.right,要不然会StackOverFlow

    }
}
